package com.tree.leetcode.dp;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName com.tree.leetcode.dp
 * Description: <类功能描述>. <br>
 * <p>
 * <使用说明>
 * </p>
 * @Author tree
 * @Date 3/9/24 11:20 PM
 * @Version 1.0
 */
public class LengthOfLongestSubstring {

    public static void main(String[] args) {
        String s = " ";
        System.out.println( lengthOfLongestSubstring1(s));

    }
    public static int lengthOfLongestSubstring(String s) {
        return lengthOfLongestSubstring1(s);
    }

    /**
    动态规划
    */
    public static int lengthOfLongestSubstring1(String s) {

        if(s == null || s.length() == 0) return 0;
        Map<Character, Integer> map = new HashMap();


        //dp[i] 代表无重复最长子串
        int[] dp = new int[s.length()];
        //初始化
        dp[0] = 1;
        map.put(s.charAt(0),0);
        int max = 1;
        for(int i =1 ; i< s.length(); i++){
            if(!map.containsKey(s.charAt(i))){
                dp[i] = dp[i-1]+1;
            }else{
                int index = map.get(s.charAt(i));
                //(i-key ) <= dp[i-1], 代表重复的项一定在内， 如果大于， 代表重复的项一定在外
                dp[i] = (i-index ) <= dp[i-1] ? (i-index) : dp[i-1]+1;
            }
            max = Math.max(max, dp[i]);
            //更新最新的字符s.charAt(i)所在的位置
            map.put(s.charAt(i), i);
        }

        return max;

    }


    public static int lengthOfLongestSubstring2(String s) {
        if(s == null) return 0;
        Map<Character, Integer> map = new HashMap();
        //最长子串
        int max = 0;
        //左边界
        int left = 0 ;

        for (int i =0 ; i< s.length(); i++){
            char c = s.charAt(i);
            /**
             * 要理解下面的代码首先要想明白获得最长字串的逻辑
             * 这里一共存在两个变量：
             *  - left：表示字串最左边字符的索引位置
             *  - i：遍历的每个字符索引位置，我们全靠这个字符来完成这道题，i这个变量存在三种情况需要考虑
             *      1） s.charAt(i)在[left, i)之间不存在重复字符
             *          - 就把s.charAt(i)放到map中，最长长度同时也加一
             *      2） s.charAt(i)在[left, i)之间存在重复字符
             *          - 获得[left, i)范围内重复字符的下标h，让left = h + 1，此时新的字串开始匹配，新的长度变成了i - left + 1 = 1
             *          - 更新map中重复字符的索引位置为i
             *      3） s.charAt(i)在[0, left)之间存在重复字符
             *          - 我们在发现重复字符后都要更新该字符在map中的索引位置，就是为了避免之前的重复元素对当前判断造成影响
             *          - 但是譬如acbba这样一个字符：当遍历到第二个b时，可知h = map.get('b')，所以h=2，那么newLeft=h+1=3;
             *              之后遍历到字符a，h = map.get('a')，发现此时h=0，newLeft=h+1=1；这种情况明显不合理，所以要求left=Math.max(left, newLeft)
             *          - 更新map中重复字符的索引位置为i，最长长度同时也加一
             *        如果当前字符 ch 包含在 map中，此时有2类情况：
             *              1）当前字符包含在当前有效的子段中，如：abca，当我们遍历到第二个a，当前有效最长子段是 abc，我们又遍历到a，
             *              那么此时更新 left 为 map.get(a)+1=1，当前有效子段更新为 bca；
             *              2）当前字符不包含在当前最长有效子段中，如：abba，我们先添加a,b进map，此时left=0，我们再添加b，发现map中包含b，
             *              而且b包含在最长有效子段中，就是1）的情况，我们更新 left=map.get(b)+1=2，此时子段更新为 b，而且map中仍然包含a，map.get(a)=0；
             *              随后，我们遍历到a，发现a包含在map中，且map.get(a)=0，如果我们像1）一样处理，就会发现 left=map.get(a)+1=1，实际上，left此时
             *              应该不变，left始终为2，子段变成 ba才对。
             *
             */
            if(map.containsKey(c)){
                left = Math.max(left,map.get(c)+1);
            }
            map.put(c,i);
            max = Math.max(max, i-left+1);

        }

        return max;

    }
}
